package pers.qianyu.month_202102.date_20210218;

/**
 * 312. 戳气球
 * https://leetcode-cn.com/problems/burst-balloons/
 *
 * @author mizzle rain
 * @date 2021-02-18 16:53
 */
public class MaxCoins {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] newArr = new int[n + 2];
        newArr[0] = 1;
        newArr[n + 1] = 1;
        System.arraycopy(nums, 0, newArr, 1, n);
        nums = newArr;
        n += 2;
        // dp[i][j] 表示开区间 (i, j) 之间
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], nums[k] * nums[i] * nums[j] + dp[i][k] + dp[k][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
}
